1. Field of the Invention
The present invention relates to path control methods adapted to autonomous system routing protocols for communication networks such as the Internet. The present invention also relates to path control systems and devices as well as path control programs.
2. Description of the Related Art
Path control protocols used for the Internet are classified into interior gateway protocols (IGP) performing path control procedures inside autonomous systems, and exterior gateway protocols (EGP) performing path control procedures between autonomous systems. Autonomous systems (AS) are networks each of which is managed by use of a single policy, wherein they are related to enterprise networks, internet service providers (ISP), or the like. The backbones of the Internet are roughly composed of intra-AS networks (each managed by a single policy) and inter-AS networks (each formed between autonomous systems).
In addition to the EGP, border gateway protocols (BGP) have been used for the Internet and disclosed in various documents such as Non-Patent Documents 1 and 2, which teach path-vector control protocols used for reception/transmission of the path control information (e.g. network addresses, AS numbers, AS path attributes, etc.) between autonomous systems, wherein UPDATE messages are included in the path control information for use in the path control procedure of the BGP.                Non-Patent Document 1: “Border Gateway Protocol 4 (BGP-4)”, IETF RFC1771, March 1995        Non-Patent Document 2: “Border Gateway Protocol 4 (BPG-4)”, IETF RFC4271, January 2006        
FIG. 17 shows a part of a packet format of an UPDATE message, which includes a path attribute full length 920, path attribute information 921, and network reachability information 922.
The path attribute full length 920 configured of two octets indicates data representing a variable length of the path attribute information 921. The path attribute information 921 includes at least an ORIGIN attribute, an AS path attribute, and a NEXT HOP address. It is possible to change the number of elements included in the path attribute information 921 with respect to each UPDATE message; hence, the path attribute information 921 has a variable length. The network reachability information 922 includes a prefix bit of an address of a network that is reachable by the present autonomous system. It is possible to incorporate a plurality of prefix bits into a single UPDATE address; hence, the network reachability information 922 has a variable length.
The path attribute information 921 includes a well-known attribute (which is requisite for any BGP router to recognize) and an option attribute (which is requisite for a prescribed BGP router to recognize). For example, the ORIGIN attribute, the AS path attribute, and the NEXT HOP address are regarded as well-known attributes which are requisite for any BGP router to recognize, while newly and arbitrarily added attributes are regarded as option attributes which are requisite for prescribed BGP routers to recognize.
When a transmission flag is set to the path attribute information 921 including an option attribute, the option attribute is attached to an UPDATE message being transmitted to a peer. When a transmission flag is not set to the path attribute information 921, the option attribute is not attached to the UPDATE message being transmitted to a peer. When a BGP router incapable of recognizing any option attribute receives an UPDATE message accompanied with a transmission flag, the BGP router neglects the option attribute by itself but attaches the option attribute to the UPDATE message being transmitted to a peer.
According to the path-vector control protocol such as the BGP, each autonomous system is informed of a path to another autonomous system on the network with reference to an UPDATE message. In a packet transfer procedure, each autonomous system determines a next-hop autonomous system corresponding to a destination address of a packet and then transfers the packet to the next-hop autonomous system. Thus, it is possible to transfer packets from one device (corresponding to a source address) to another device (corresponding to a destination address).
The path control procedure of the BGP preferentially designates a path having a minimum number of hops (or a minimum AS-path length) while arbitrarily selecting other paths with reference to various policies. Herein, policies adapted to autonomous systems include decisions as to whether to permit connections with adjacent autonomous systems or decisions as to which connections are to be preferentially used, wherein they are autonomously determined by autonomous systems.
BGP routers are used to perform transactions of the path control information by way of the path control procedure of the BGP. Autonomous systems are networks each managed by a single policy and are formed using various routers, end-user terminals, etc. Among routers forming autonomous systems, BGP routers are used to perform communications between autonomous systems in accordance with the BGP. For the sake of simplification of the description, each autonomous system is presumably equivalent to a single BGP router unless any distinction is defined between the autonomous system and the router.
A packet transfer procedure will be described in connection with a path control procedure of a path-vector control protocol. FIG. 18 is a diagram used for explaining a packet transfer procedure adapted to the path control procedure of the path-vector control protocol. Specifically, FIG. 18 shows an example of an inter-AS network topology (or a BGP network topology) applied between autonomous systems performing transactions of the path control information by way of reception/transmission of UPDATE messages. Herein, each circle designates each autonomous system (AS), and each line laid between circles designates a connection between autonomous systems.
The number assigned to each circle is an AS number which is uniquely assigned to each AS on the network. In actual communications over the Internet, globally unique numbers are assigned to AS numbers. In this connection, an autonomous system whose AS number is “1” is designated by a reference symbol “AS1”; hence, FIG. 18 includes seven autonomous systems, namely, AS1 to AS7.
Rectangular blocks attached to circles (designating prescribed autonomous systems) designate node path tables 930 to 935, which are stored in memories of prescribed autonomous systems (i.e., BGP routers). Specifically, they designate the AS path information with respect to a prefix of address “192.170.0.0/16” issued by the AS1. The upper portions of the node path tables 930 to 935 show full paths stored in prescribed autonomous systems with respect to the prefix of address “192.170.0.0/16”, while the lower portions thereof show packet transfer destinations (i.e. next hops) via best paths (each having a minimum number of hops) with respect to the prefix of address “192.170.0.0/16”.
When the AS6 receives a packet with respect to the prefix of address “192.170.0.0/16”, the AS6 consults the node path table 934 so as to designate the AS5 as the packet transfer destination with respect to the prefix of address “192.170.0.0/16”. Thus, the AS6 transfers a packet to the AS5 with respect to the prefix of address “192.170.0.0/16” (see an arrow 940 in FIG. 18).
Upon reception of the packet from the AS6, the AS5 consults the node path table 933 so as to designate the AS4 as a transfer destination of the packet with respect to the prefix of address “192.170.0.0/16”. Then, the AS5 transfers the packet to the AS4. According to similar procedures, the AS4 transfers the packet from the AS5 to the AS1.
Upon reception of the packet from the AS4, the AS1 acknowledges that the transfer destination of the packet is directed to the prefix of address “192.170.0.0/16” which is issued by itself, hence, the AS1 accepts the packet.
As described above, best paths are determined based on the path control information, and transfer destinations of packets are used as the routing information, thus completing transfer procedures of packets from source nodes to destination nodes.
In the path control procedure of the path-vector control protocol for transferring packets in accordance with the path control information that is managed based on the path attribute information (e.g. the path length), autonomous systems are informed of paths toward other nodes on the network by way of transactions of the path control information. Herein, autonomous systems repeat sending UPDATE messages of the BGP to adjacent autonomous systems in accordance with their policies, thus spreading UPDATE messages over the network. Hereinafter, spreading UPDATE messages will be referred to as “global notification”.
The existing Internet suffers from the increasing amount of path control information. In particular, inter-AS networks suffer from the increasing amount of path control information due to multi-homing and traffic engineering (referred to as “TE”). Multi-homing refers to each autonomous system transferring an UPDATE message regarding the same prefix of address over the network via connections established with other autonomous systems, thus achieving traffic dispersions and improving contingency resistance by way of plural paths directed to the prefix of the address. Traffic engineering (TE) refers to each autonomous system spreading fragments of one prefix of address over the network via connections established with other autonomous systems, thus achieving traffic dispersions and improving security. Recently, multi-homing and traffic engineering have been frequently used in the existing Internet requiring high security and high-speed communications. On the other hand, they increase the scale of path information databases of routers and also increase UPDATE messages transferred between autonomous systems.
Next, the technical feature of traffic engineering-will be described in conjunction with increasing UPDATE messages. FIG. 19 is a diagram used for explaining the technical feature of traffic engineering and the increasing UPDATE message. Similar to FIG. 18, FIG. 19 shows connections between seven autonomous systems, i.e. AS1 to AS7. The AS1 globally notifies the AS2 and AS4 with the prefix of address “192.170.0.0/16” by way of multi-homing on the network shown in FIG. 19. The following description is made under a precondition in which the AS1 performs an address control procedure so as to receive traffic directed to the prefix of address “192.170.0.0/16” from the AS2. In this connection, the logical sum between “192.170.0.0/17” and “192.170.128.0/17” goes to “192.170.0.0/16”.
The AS1 sends an UPDATE message of the prefix of address “192.170.128.0/17” to the AS2 serving as a peer of the AS1 via a dotted arrow 950 in FIG. 19, thus globally notifying it over the network. This makes it possible for the AS1 to receive traffic directed to the prefix of address “192.170.128.0/17” from the AS2.
The above traffic engineering is applied to the AS1 for the purpose of the reception of traffic directed to the prefix of address “192.170.128.0/17” from the AS2. It is not directly aimed at the load balance and traffic control in the inter-AS network following the AS2. The UPDATE message used for traffic engineering should be increased due to the global notification toward other autonomous systems following the AS2. This likely causes the UPDATE message exceeding a prescribed value requisite for traffic engineering to flow over the inter-AS network. Increasing the UPDATE message imposes additional loads to path processing of each autonomous system and makes the network unstable due to incomplete convergence of the path control information in each autonomous system. In addition, notifying numerous fragmentations of the prefix of address over the network increases the scale of path information databases of routers.
In the above circumstances, the present inventors have recognized that the path control procedures of path control protocols increase UPDATE messages so as to impose additional loads to routers of autonomous systems, thus making the path control information unstable. The “unstable” path control information may cause improper routing operations so as to prevent packets from reliably reaching destination nodes, thus causing packet losses. In addition, it increases the scale of path information databases of routers, which in turn increases loads to routers.
One reason for increasing UPDATE messages is related to the path control method employing traffic engineering. Normally, traffic engineering intends to circumscribe the path control range thereof to only the peers of autonomous systems. The conventional path control procedures of path control protocols globally notify UPDATE messages over the network in order to control traffics of peers. This increases UPDATE messages and also increases processing loads of routers in autonomous systems, thus making the network unstable.